/*
 * $Id: HashList.hpp 50 2009-02-10 05:48:05Z hyunghwan.chung $
 *
   Copyright 2005-2009 Chung, Hyung-Hwan.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an  BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

#ifndef _XP_BAS_HASHLIST_CLASS_
#define _XP_BAS_HASHLIST_CLASS_

#include <xp/types.h>
#include <xp/bas/assert.h>
#include <xp/Hashable.hpp>
#include <xp/bas/LinkedList.hpp>

XP_BEGIN_NAMESPACE2 (xp, bas)

template<typename T>
struct HashListHasher
{
	size_t operator() (const T& v) const
	{
		return v.hashCode();
	}
};

template <typename T, typename HASHER = HashListHasher<T> > class HashList
{
public:
	typedef LinkedList<T> DatumList;
	typedef typename DatumList::Node Node;

	HashList (
		xp_size_t node_capacity = 10, 
		xp_size_t load_factor = 75, 
		xp_size_t mpb_size = 0)/*: datum_list (mpb_size)*/
	{
		this->nodes = XP_NULL;
		this->node_capacity = 0;
		this->datum_list = XP_NULL;

		try {
			this->nodes = new Node*[node_capacity << 1];
			this->node_capacity = node_capacity;
			for (xp_size_t i = 0; i < node_capacity << 1; i++) {
				this->nodes[i] = XP_NULL;
			}

			this->datum_list = new LinkedList<T> (mpb_size);
		}
		catch (...) {
			if (this->nodes != XP_NULL) {
				delete[] this->nodes;
				this->node_capacity = 0;
				this->nodes = XP_NULL;
			}

			if (this->datum_list != XP_NULL) {
				delete this->datum_list;
				this->datum_list = XP_NULL;
			}
			throw;
		}

		this->load_factor = load_factor;
		this->threshold   = node_capacity * load_factor / 100;
	}

	HashList (const HashList<T>& list)/*: 
		datum_list (list.datum_list.mpBlockSize()) */
	{
		this->nodes = XP_NULL;
		this->node_capacity = 0;
		this->datum_list = XP_NULL;

		try {
			this->nodes = new Node*[list.node_capacity << 1];
			this->node_capacity = list.node_capacity;
			for (xp_size_t i = 0; i < list.node_capacity << 1; i++) {
				this->nodes[i] = XP_NULL;
			}

			this->datum_list = new LinkedList<T> (list.datum_list->mpBlockSize());
		}
		catch (...) {
			if (this->nodes != XP_NULL) {
				delete[] this->nodes;
				this->node_capacity = 0;
				this->nodes = XP_NULL;
			}
			if (this->datum_list != XP_NULL) {
				delete this->datum_list;
				this->datum_list = XP_NULL;
			}
			throw;
		}

		this->load_factor = list.load_factor;
		this->threshold   = list.threshold;

		for (xp_size_t i = 0; i < list.node_capacity; i++) {
			xp_size_t head = i << 1;
			xp_size_t tail = head + 1;

			Node* np = list.nodes[head];
			if (np == XP_NULL) continue;
			
			do {
				copy_datum (
					np, this->node_capacity, 
					this->nodes, this->datum_list);
				if (np == list.nodes[tail]) break;
				np = np->forward ();
			} while (1);
		}
	}

	~HashList ()
	{
		this->clear ();
		if (this->nodes) delete[] this->nodes;
		if (this->datum_list) delete this->datum_list;
	}

	HashList<T>& operator= (const HashList<T>& list)
	{
		if (this != &list)
		{
			this->clear ();

			for (xp_size_t i = 0; i < list.node_capacity; i++) {
				xp_size_t head = i << 1;
				xp_size_t tail = head + 1;

				Node* np = list.nodes[head];
				if (np == XP_NULL) continue;
				
				do {
					this->copy_datum (
						np, this->node_capacity, 
						this->nodes, this->datum_list);
					if (np == list.nodes[tail]) break;
					np = np->forward ();
				} while (1);
			}
		}

		return *this;
	}

	Node* set (const T& datum, bool overwrite = true)
	{
		xp_size_t hc, head, tail;
		Node* np;

		hc = this->hasher(datum) % node_capacity;
		head = hc << 1; tail = head + 1;

		np = nodes[head];
		if (np != XP_NULL) 
		{
			do 
			{
				T& t = np->value;
				if (datum == t) 
				{
					if (!overwrite) return XP_NULL;
					t = datum;
					return np;
				}

				if (np == nodes[tail]) break;
				np = np->forward ();
			} while (1); 
		}

		if (datum_list->size() >= threshold) 
		{
			this->rehash ();
			hc = this->hasher(datum) % node_capacity;
			head = hc << 1; tail = head + 1;
		}

		if (nodes[head] == XP_NULL) 
		{
			this->nodes[head] = this->datum_list->insertValue (XP_NULL, datum);
			this->nodes[tail] = this->nodes[head];
		}
		else 
		{
			this->nodes[head] = datum_list->insertValue (this->nodes[head], datum);
		}

		return this->nodes[head];
	}

	T* setValue (const T& datum, bool overwrite = true)
	{
		// identical to setValue except that it returns 
		// the pointer to the value
		return &set(datum, overwrite)->value;
	}

	Node* insert (const T& datum)
	{
		return this->set (datum, false);
	}

	Node* upsert (const T& datum)
	{
		return this->set (datum, true);
	}


	Node* update (const T& datum)
	{
		Node* node = this->nodeOf (datum);
		if (node) node->value = datum;
		return node;
	}

	Node* nodeOf (const T& datum)
	{
		xp_size_t hc, head, tail;
		Node* np;

		hc = this->hasher(datum) % node_capacity;
		head = hc << 1; tail = head + 1;

		np = this->nodes[head];
		if (np) {
			do {
				T& t = np->value;
				if (datum == t) return np;
				if (np == nodes[tail]) break;
				np = np->forward ();
			} while (1);
		}

		return XP_NULL;
	}

	const Node* nodeOf (const T& datum) const
	{
		xp_size_t hc, head, tail;
		Node* np;

		hc = this->hasher(datum) % node_capacity;
		head = hc << 1; tail = head + 1;

		np = this->nodes[head];
		if (np != XP_NULL) {
			do {
				T& t = np->value;
				if (datum == t) return np;
				if (np == nodes[tail]) break;
				np = np->forward ();
			} while (1);
		}

		return XP_NULL;
	}

	T* valueOf (const T& datum)
	{
		Node* b = nodeOf (datum);
		if (b == XP_NULL) return XP_NULL;
		return &b->value;
	}

	const T* valueOf (const T& datum) const
	{
		const Node* b = nodeOf (datum);
		if (b == XP_NULL) return XP_NULL;
		return &b->value;
	}

	bool contains (const T& datum) const
	{
		return nodeOf (datum) != XP_NULL;
	}

	int remove (const T& datum)
	{
		xp_size_t hc, head, tail;
		Node* np;

		hc = this->hasher(datum) % node_capacity;
		head = hc << 1; tail = head + 1;

		np = this->nodes[head];
		if (np != XP_NULL) {
			do {
				T& t = np->value;
				if (datum == t) {
					if (nodes[head] == nodes[tail]) {
						xp_assert (np == nodes[head]);
						nodes[head] = nodes[tail] = XP_NULL;
					}	
					else if (np == nodes[head])
						nodes[head] = np->forward();
					else if (np == nodes[tail]) 
						nodes[tail] = np->backward();

					datum_list->remove (np);
					return 0;
				}

				if (np == nodes[tail]) break;
				np = np->forward ();
			} while (1);
		}

		return -1;
	}

	void clear ()
	{
		for (xp_size_t i = 0; i < (node_capacity << 1); i++) 
		{
			this->nodes[i] = XP_NULL;
		}
		if (this->datum_list) this->datum_list->clear ();
	}

	Node* head () const
	{
		return datum_list->head();
	}

	Node* tail () const
	{
		return datum_list->tail();
	}

	typedef int (HashList<T>::*TraverseCallback) (Node* start, Node* cur);

	void traverse (TraverseCallback callback, Node* start)
	{
		Node* cur, *backward, * forward;

		cur = start;
		while (cur != XP_NULL) {
			backward = cur->backward ();
			forward = cur->forward ();

			int n = (this->*callback) (start, cur);

			if (n > 0) cur = forward;
			else if (n < 0) cur = backward;
			else break;
		}
	}

	xp_size_t capacity() const
	{
		return this->node_capacity;
	}

	xp_size_t size () const
	{
		return this->datum_list->size();
	}

	MemoryPool& getMemoryPool ()
	{
		return this->datum_list->getMemoryPool();
	}

protected:
	mutable xp_size_t node_capacity;
	mutable Node** nodes;
	mutable DatumList* datum_list;
	mutable xp_size_t threshold;
	xp_size_t load_factor;
	HASHER hasher;

	void rehash () 
	{

		/*
		HashList<T> temp (node_capacity << 1, load_factor, datum_list->mpBlockSize());
		Node* p = this->head();
		while (p != XP_NULL)
		{
			temp.set (p->value);
			p = p->forward ();
		}

		// swap the contents
		xp_size_t temp_capa = temp.node_capacity;
		Node** temp_nodes = temp.nodes;
		DatumList* temp_datum_list = temp.datum_list;
		xp_size_t temp_threshold = temp.threshold;
		xp_size_t temp_load_factor = temp.load_factor;

		temp.node_capacity = this->node_capacity;
		temp.nodes = this->nodes;
		temp.datum_list = this->datum_list;
		temp.threshold = this->threshold;
		temp.load_factor = this->load_factor;

		this->node_capacity = temp_capa;
		this->nodes = temp_nodes;
		this->datum_list = temp_datum_list;
		this->threshold = temp_threshold;
		this->load_factor = temp_load_factor;
		*/

		MemoryPool& mpool = this->getMemoryPool ();
		// Move nodes around instead of values to prevent
		// existing values from being copied over and destroyed.
		// this incurs less number of memory allocations also.
		//HashList<T> temp (this->node_capacity << 1, this->load_factor, this->datum_list->mpBlockSize());
		HashList<T> temp (this->node_capacity << 1, this->load_factor, 0);
		Node* p = this->datum_list->head();
		while (p)
		{
			Node* next = p->forward();

			// p->value must be a unique value in the existing hashed list.
			// i can safely skip checking existing values.

			// detach the existing node.
			Node* pp = this->datum_list->yield (p, true);

			// get the hash code using the new capacity
			xp_size_t hc, head, tail;
			hc = this->hasher(pp->value) % temp.node_capacity;
			head = hc << 1; tail = head + 1;

			// insert the detached node to the new temporary list
			if (temp.nodes[head]) 
			{
				temp.nodes[head] = temp.datum_list->insertNode (temp.nodes[head], pp);
			}
			else 
			{
				temp.nodes[head] = temp.datum_list->insertNode (XP_NULL, pp);
				temp.nodes[tail] = temp.nodes[head];
			}

			p = next;
		}

		// all nodes must have been popped out.
		XP_ASSERT (this->datum_list->size() <= 0);

		// clear the node pointers by force as no nodes exist in the old list.
		for (xp_size_t i = 0; i < (this->node_capacity << 1); i++) 
		{
			this->nodes[i] = XP_NULL;
		}

		mpool.swap (temp.getMemoryPool());

		// swap the contents
		xp_size_t temp_capa = temp.node_capacity;
		Node** temp_nodes = temp.nodes;
		DatumList* temp_datum_list = temp.datum_list;
		xp_size_t temp_threshold = temp.threshold;
		xp_size_t temp_load_factor = temp.load_factor;

		temp.node_capacity = this->node_capacity;
		temp.nodes = this->nodes;
		temp.datum_list = this->datum_list;
		temp.threshold = this->threshold;
		temp.load_factor = this->load_factor;

		this->node_capacity = temp_capa;
		this->nodes = temp_nodes;
		this->datum_list = temp_datum_list;
		this->threshold = temp_threshold;
		this->load_factor = temp_load_factor;
	}

	void copy_datum (
		Node* np, xp_size_t new_node_capa,
		Node** new_nodes, DatumList* new_datum_list) const
	{
		T& t = np->value;

		xp_size_t hc = hasher(t) % new_node_capa;
		xp_size_t head = hc << 1;
		xp_size_t tail = head + 1;

		if (new_nodes[head] == XP_NULL) 
		{
			new_nodes[head] =
				new_datum_list->insertValue (XP_NULL, t);
			new_nodes[tail] = new_nodes[head];
		}
		else 
		{
			new_nodes[head] =
				new_datum_list->insertValue (new_nodes[head], t);
		}
	}

};

XP_END_NAMESPACE2 (xp, bas)

#endif
